这道题显然是最短路,但是似乎转向时不好处理,于是我们要用到分层图。
实现很简单,建立两层图,第一层记录横向边,第二层记录纵向边,相同的关键点两层图连一条费用为1的边。
还有,这道题只需要在关键点之间连边(非关键点无法转向,连了也没用),路径长度为坐标差*2。
An Ac a day, keeps the doctor away!
这道题显然是最短路,但是似乎转向时不好处理,于是我们要用到分层图。
实现很简单,建立两层图,第一层记录横向边,第二层记录纵向边,相同的关键点两层图连一条费用为1的边。
还有,这道题只需要在关键点之间连边(非关键点无法转向,连了也没用),路径长度为坐标差*2。
这道题貌似很多人用的是网络流+分层图。这里介绍一种费用流解法。
可以证明,最后一个人到达的时间是小于第100天的。
那么对于每一趟航班,如果他的起点是u,终点为v,可搭乘的人的数量为w。那我们就对(u,v)连100条流量为w,费用为i的边(i表示第几天),分别表示第i天的航班。
显然,在一个强联通分量中,只要有一个城市与s联通,那么整个分量就与s联通。
于是我们可以缩点,统计它的入度。如果入度为0,我们就从s向这个缩点连一条边,如果入度不为0,说明其他城市可以到达它,我们就不需要单独连边。
最后,注意特判与s在同一强联通分量的点。
i=1∑nj=1∑mlcm(i,j)
首先,我们得知道过原点与两点的抛物线解析式:
设该函数解析式为 y=ax2+bx+c(a<0)且过 (0,0),(x1,y1),(x2,y2) 三点。
由函数过 (0,0) 得 c=0。
对于每个位置 i , 我们向 pi 连一条边。 结合题意可知,一个合法的排列,是一个由 n 个自环组成的图。
但现在会形成多个环,不妨记环的数量为 k , 第 i 个环的大小为 si(包括自环)。
我们现在要做的,就是将这 k 个环拆成 n 个自环。